//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
// 示例 1:
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 示例 2:
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 提示:
// 1 <= s.length, p.length <= 3 * 10⁴
// s 和 p 仅包含小写字母
// Related Topics 哈希表 字符串 滑动窗口 👍 814 👎 0

package leetcode.editor.cn;

import java.util.*;

class FindAllAnagramsInAString {
    public static void main(String[] args) {
        Solution solution = new FindAllAnagramsInAString().new Solution();
//        solution.findAnagrams("abab", "ab");
//        solution.findAnagrams("cbaebabacd", "abc");
        solution.findAnagrams("cbaebabacd", "abc");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 失败（超时wuwu~~）想复杂了
         * @param s
         * @param p
         * @return
         */
        /*
        public List<Integer> findAnagrams(String s, String p) {
            HashMap<Object, Integer> map = new HashMap<>();
            List<Integer> list = new ArrayList<>();
            int left = 0, right = 0;
            map = toMap(p);
            while (left < s.length() && right < s.length()) {
                if (right - left < p.length()) {
                    if (map.containsKey(s.charAt(right))) {
                        map.put(s.charAt(right), map.getOrDefault(s.charAt(right), 0) - 1);
                        // 等于0，直接清除
                        if (map.get(s.charAt(right)) == 0) {
                            map.remove(s.charAt(right));
                        }
                    }
                    if (map.size() == 0) {
                        list.add(left);
                        left++;
                        right = left;
                        // 重新将p放入map
                        map = toMap(p);
                    }
                    else {
                        right++;
                    }
                } else {
                    left++;
                    right = left;
                    // 更新map
                    map = toMap(p);
                }
            }
            return list;
        }

        public HashMap<Object, Integer> toMap(String str) {
            HashMap<Object, Integer> map = new HashMap<>();
            // 将p字符放入map中进行判断
            for (int i = 0; i < str.length(); i++) {
                map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
            }
            return map;
        }
         */

        /**
         * 固定的滑动窗口
         *
         * @param s
         * @param p
         * @return
         */
        /*public List<Integer> findAnagrams(String s, String p) {
            int[] record = new int[26]; // hash表记录重复的字符
            // 将p放入hash表中进行判断
            for (int i = 0; i < p.length(); i++) {
                record[p.charAt(i) - 'a']++;
            }

            int right = 0;
            int left = 0;
            List<Integer> list = new ArrayList<>();
            // 滑动窗口中的字符映射的数组
            int[] windows = new int[26];
            while (right < s.length()) {
                // 将字符放入数组
                windows[s.charAt(right) - 'a']++;
                // 在固定的滑动窗口进行判断
                if (right - left + 1 == p.length()) {
                    // 如果窗口中的hash数组和p的hash数组相等，即将窗口左侧加入即可
                    if (Arrays.equals(windows, record)) {
                        list.add(left);
                    }
                    // 窗口不匹配时
                    // 因为是固定长度，将left中的字符删除，将left向右移动即可
                    windows[s.charAt(left) - 'a']--;
                    left++;
                }
                right++;
            }
            return list;
        }*/

        /**
         * TODO 使用固定的滑动窗口和hash表即可
         *
         * @param s
         * @param p
         * @return
         */
        /*public List<Integer> findAnagrams(String s, String p) {
            // p的hash表
            int[] record = new int[26];
            // 滑动窗口的哈希表
            int[] window = new int[26];
            List<Integer> indexList = new ArrayList<>();

            // 先将p放入哈希表
            for (int i = 0; i < p.length(); i++) {
                record[p.charAt(i) - 'a'] += 1;
            }

            // 左右窗口滑动
            int left = 0, right = 0;
            for (; right < s.length(); right++) {
                // 右界的字符加入哈希表
                window[s.charAt(right) - 'a'] += 1;
                // 固定的滑动窗口，不用while
                if (right - left + 1 == p.length()) {
                    // 两个哈希表相等，说明找到了，使用mao和set不是很容易判断
                    if (Arrays.equals(window, record)) {
                        // 此时记录最左边的索引
                        indexList.add(left);
                    }
                    // 修改滑动窗口的哈希表
                    window[s.charAt(left) - 'a'] -= 1;
                    // 窗口向右移动，不满足同分异构也要移动窗口，保持固定的滑动窗口
                    left++;
                    // for循环就不用 right++ 了
                }
            }
            return indexList;
        }*/
        public List<Integer> findAnagrams(String s, String p) {
            // p的hash表
            Map<Character, Integer> map = new HashMap<>();
            // 滑动窗口的hash表
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0, valid = 0;
            List<Integer> res = new ArrayList<>();

            for (int i = 0; i < p.length(); i++) {
                map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
            }

            while (right < s.length()) {
                char c = s.charAt(right);
                if (map.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (map.get(c).equals(window.get(c))) {
                        valid++;
                    }
                }

                right++;

                while (right - left == p.length()) {
                    if (valid == map.size()) res.add(left);

                    char c1 = s.charAt(left);
                    if (map.containsKey(c1)) {
                        if (map.get(c1).equals(window.get(c1))) {
                            valid--;
                        }
                        window.put(c1, window.getOrDefault(c1, 0) - 1);
                    }

                    left++;
                }
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
